package main

import "fmt"

var _ = `
560. 和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。

示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107


//举个例子:
int[] a = {1, 2, 3, 4, 5, 6};

//将每个元素累加,对应下面这个数组:
int[] b =     {1, 3, 6, 10, 15, 21};
int[] b = {0, 1, 3, 6, 10, 15, 21};

//因为题干要求是连续子数组,所以任意的b[i]与b[j]的差值即为子数组的和.
//所以就变成了找出b[i]与b[j]的差等于k,有多少种组合方式.

//第一题是找两数之和a+b=target，这题是找两数之差a-b=target

//因为是求有多少种组合，所以key是元素，value是次数，次数初始化全是1

`

func subarraySum(nums []int, k int) int {
	res := 0

	// 前缀和
	preSum := make([]int, len(nums)+1)
	m := make(map[int]int) // map{ sum: count }

	preSum[0] = 0
	for i, v := range nums {
		preSum[i+1] = preSum[i] + v
	}

	// 求preSum里面,两数之差为k的个数
	for i := 0; i < len(preSum); i++ {
		// pre[i] - x = k => x = pre[i] - k
		target := preSum[i] - k
		if _, ok := m[target]; ok {
			res += m[target]
		}
		// 从前向后,判断当前值后,再把当前值加进去
		m[preSum[i]]++
	}

	return res
}

func main() {

	nums := []int{1, 2, 3}
	k := 3
	fmt.Println(subarraySum(nums, k))
}
